import java.util.*;

public class f {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), q = sc.nextInt();
        int[] a = new int[n];
        Arrays.setAll(a, k -> sc.nextInt());
        FenwickTree[] tr = new FenwickTree[12];
        Arrays.setAll(tr, k -> new FenwickTree(n));
        for (int i = 0; i < n; ++i) {
            int x = f(a[i]);
            tr[x].update(i + 1, 1);
//             System.out.println("tr" + Arrays.toString(tr[x].data));
        }
//         System.out.println("#" + tr[11].query(n));
        for (int i = 0; i < q; ++i) {
            int op = sc.nextInt();
            int x = sc.nextInt(), y = sc.nextInt();
            if (op == 1) {
                int oldValue = f(a[x - 1]);
                int newValue = f(y);
                tr[oldValue].update(x, -1);
                tr[newValue].update(x, 1);
                a[x - 1] = y;
            } else {
                int[] res = new int[12];
                for (int j = 0; j < 12; ++j) {
                    res[j] = tr[j].query(y) - tr[j].query(x - 1);
                }
                long ans = 0;
                for (int u = 0; u < 12; ++u) {
                    for (int v = 0; v <= u; ++v) {
                        if ((u | v) % 4 == 3 && (u >> 2) + (v >> 2) >= 2) {
                            if (v < u) {
                                ans += (long) res[u] * res[v];
                            } else {
                                ans += res[u] * (res[u] - 1L) / 2;
                            }
                        }
                    }
                }
//                 System.out.println(Arrays.toString(res));
                System.out.println(ans);
            }
        }
    }
    static int f(int x) {
        int res = 0;
        int c = 0;
        while (x % 3 == 0) {
            c++;
            x /= 3;
        }
        res |= Math.min(c, 2) << 2;
        if (x % 5 == 0) {
            res |= 2;
        }
        if (x % 11 == 0) {
            res |= 1;
        }
        return res;
    }
}
class FenwickTree {
    int n;
    int[] data;
    FenwickTree (int n) {
        this.n = n;
        data = new int[n + 1];
    }
    void update(int x, int d) {
        for (int i = x; i <= n; i += i & -i) {
            data[i] += d;
        }
    }
    int query(int x) {
        int res = 0;
        while (x > 0) {
            res += data[x];
            x -= x & -x;
        }
        return res;
    }
}
